package cn.tedu.six2202.day07;

public class BinarySearchTree<E extends Comparable<E>> {
    //根节点
    private Node root;

    //添加元素
    public boolean add(E e){
        //判断root是否为null
        if (root==null) {
            root = new Node(e);
            return true;
        }
        //root不为null
        return root.append(e);
    }

    //定义内部类表示节点
    private class Node{
        private E ele;  //节点中保存的元素对象
        private Node left;  //左子树指向的节点
        private Node right;  //右子树指向的节点

        //定义有参构造方法,用于创建节点
        Node(E ele){
            this.ele = ele;
        }

        //向某个节点上添加给定的元素,尝试让新元素称为其左/右子树
        public boolean append(E e) {
            //判断e和节点的元素是否相等,若相等,则添加失败,返回false
            if (e.compareTo(ele)==0)
                return false;
            else if(e.compareTo(ele)<0){  //尝试向ele的left上添加节点
                //判断left是否为null,为null,则让新元素成为left节点
                if (left==null) {
                    left = new Node(e);
                    return true;
                }
                return left.append(e);
            } else {  //尝试向ele的right添加节点
                if (right==null){
                    right = new Node(e);
                    return true;
                }
                return right.append(e);
            }
        }
    }





}
